[% setvar title Objects : Native support for multimethods %]
<div id="archive-notice">
    <h3>This file is part of the Perl 6 Archive</h3>
    <p>To see what is currently happening visit <a href="http://www.perl6.org/">http://www.perl6.org/</a></p>
</div>
<div class='pod'>
<a name='TITLE'></a><h1>TITLE</h1>
<p>Objects : Native support for multimethods</p>
<a name='VERSION'></a><h1>VERSION</h1>
<pre>  Maintainer: Damian Conway &lt;<a href='mailto:damian@conway.org'>damian@conway.org</a>&gt;
  Date: 18 September 2000
  Last Modified: 25 Sep 2000
  Mailing List: <a href='mailto:perl6-language-objects@perl.org'>perl6-language-objects@perl.org</a>
  Number: 256
  Version: 2
  Status: Frozen</pre>
<a name='ABSTRACT'></a><h1>ABSTRACT</h1>
<p>This RFC proposes that Perl natively support multiply dispatched
subroutines (multimethods).</p>
<a name='DESCRIPTION'></a><h1>DESCRIPTION</h1>
<p>Multimethods solve a class of problems in which objects of two or more
hierarchies must interact polymorphically, but where the nature of the
interaction is determined by the run-time type of <i>both</i> (<i>all</i>) the
objects.</p>
<a name='Theoretical model'></a><h2>Theoretical model</h2>
<p>It is proposed that calls to certain (explicitly marked) subroutines be
dispatched using a different mechanism from that used for regular Perl 5
subroutines, or that used for Perl 5 methods.</p>
<p>These explicitly marked subroutines would share the same name, but
provide unique parameter lists. Collectively all marked subroutines
with the same name but different parameters lists would be known
as a <i>multimethod</i>, with each individual subroutine known as a
<i>variant</i> of the multimethod.</p>
<p>The new dispatch mechanism would look at the classes or types of each
argument to the subroutine (by calling <code>ref</code> on each) and determine
the &quot;closest&quot; matching variant of the multimethod, according to the
parameter types specified in the variants' parameter list.</p>
<p>The result would subsume the behaviour of function overloading (e.g. in
C++) but in a more sophisticated manner, since multimethods take the
run-time inheritance relationships of each argument into account.
Another way of thinking of the mechanism is that it would perform
polymorphic dispatch on every argument of a multimethod, not just on
the first.</p>
<a name='Defining multimethods'></a><h2>Defining multimethods</h2>
<p>A single variant of a multimethod would be defined by specifying a
subroutine with a full parameter list (as per RFC 128), and
appending the attribute <code>:multi</code>. Two or more such subroutines
could be defined with the same name, in the same package namespace, provide
they were both defined with the <code>:multi</code> attribute, and their parameter
lists were not identical.</p>
<p>For example:</p>
<pre>	package LargeNum;
	package LargeInt;    use base 'LargeNum';
	package LargeFloat;  use base 'LargeNum';

	package LargeMath;

        sub divide(LargeInt $a, LargeInt $b) : multi {
		...
	}

        sub divide(LargeInt $a, LargeFloat $b) : multi {
		...
	}</pre>
<p>This creates a (single) multimethod called <code>LargeMath::divide</code> with two
variants. If the multimethod is called with two references to LargeInt
objects as arguments:</p>
<pre>	$x = LargeInt-&gt;new(1234567890);
	$y = LargeInt-&gt;new(9876543210);
	$quotient = divide($x, $y);</pre>
<p>then the first variant is invoked. If the multimethod
is called with a LargeInt reference and a LargeFloat reference:</p>
<pre>	$x = LargeInt-&gt;new(1234567890);
	$y = LargeFloat-&gt;new(9876543210.12345);
	$quotient = divide($x, $y);</pre>
<p>then the second variant is called.</p>
<p>Calling the multimethod with any other combination of LargeNum-derived
reference arguments (e.g. a reference to a LargeFloat and a reference
to a LargeInt, or two LargeFloat references) results in an exception
being thrown, with the message:</p>
<pre>	No viable candidate for call to multimethod divide</pre>
<p>To avoid this, a &quot;catch-all&quot; variant could be specified:</p>
<pre>	sub divide(LargeNum $b, LargeNum $b) : multi {
		...
	}</pre>
<p>Now, calling <code>divide</code> with (for example) a LargeFloat
reference and a LargeInt reference causes this third variant to be
invoked. That's because a LargeFloat <i>is-a</i> LargeNum (so the first
argument is compatible with the first parameter), and a LargeInt <i>is-a</i>
LargeNum too (so the second argument is compatible with the second
parameter). Note that adding this third variant doesn't affect calls
to the other two, since multiple dispatch always selects the nearest
match.</p>
<a name='Finding the &quot;nearest&quot; multimethod'></a><h2>Finding the &quot;nearest&quot; multimethod</h2>
<p>The usefulness of multiple dispatch depends on how intelligently the
dispatcher decides which variant of a multimethod is &quot;nearest&quot; to a
given set of arguments. That decision process is called <i>dispatch
resolution</i>, and it is proposed that it be done (or <i>appear</i> to be done,
modulo optimization) like this:</p>
<ul>
<li><a name='1.'></a>1.</li>
<p>If the types of the arguments given (as determined by applying <code>ref</code>
to each in turn) exactly match the set of parameter types
specified in any variant of the multimethod, that variant is
immediately called.</p>
<li><a name='2.'></a>2.</li>
<p>Otherwise, the dispatch mechanism compiles a list of viable targets.
A viable target is a variant of the multimethod with the same
number of parameters as there were arguments passed. In addition,
for each parameter the specified parameter type must be a base
class of the actual type of the corresponding argument in the
actual call (i.e. each argument must belong to a subclass of the
corresponding parameter type).</p>
<li><a name='3.'></a>3.</li>
<p>If there is only one viable target, it is called immediately. If
there are no viable targets, an exception is thrown indicating
that the multimethod can't handle the specific set of arguments.
(but see <i><a href='#Handling dispatch failure'>&quot;Handling dispatch failure&quot;</a></i> below).</p>
<li><a name='4.'></a>4.</li>
<p>Otherwise, the dispatch mechanism examines each viable target and
computes its inheritance distance from the actual set of
arguments. The inheritance distance from a single argument to the
corresponding parameter is the number of inheritance steps between
their respective classes (working up the tree from argument to
parameter). If there's no inheritance path between them, the
distance is infinite. The inheritance distance for a set of
arguments is just the sum of their individual inheritance
distances.</p>
<li><a name='5.'></a>5.</li>
<p>The dispatch mechanism then chooses the viable target with the
smallest inheritance distance as the actual target. If more than
one viable target has the same smallest distance, the call is
ambiguous. In that case, the dispatch process fails and an
exception is thrown (but see <i><a href='#Handling dispatch failure'>&quot;Handling dispatch failure&quot;</a></i> below)
If there's only a single actual target, its identity is cached
(to accelerate subsequent dispatching), and then the actual target is
invoked.</p>
</ul>
<a name='Handling built-in types'></a><h2>Handling built-in types</h2>
<p>Because the multiple dispatch mechanism applies <code>ref</code> to determine
the type of each argument, it is indifferent to whether those
arguments are references to blessed objects, or just regular Perl data
types. That means that multimethod variants can also be defined to process
built-in data types:</p>
<pre>        sub stringify(ARRAY $a) : multi {
                my @arg = map { stringify $_ } @a;
                return  &quot;[&quot; . join(&quot;, &quot;,@a) . &quot;]&quot;;
        }

        sub stringify(HASH $h) : multi {
                my %arg = map { stringify $_ } %h;
                return  &quot;{&quot; . join(&quot;, &quot;, map( &quot;$_=&gt;$h{$_}&quot;, keys %h) ) . &quot;}&quot;;
        }

        sub stringify(CODE $c) : multi {
                return &quot;sub {???}&quot;;
        }

        sub stringify(Regexp $r) : multi {
                return &quot;qr/$r/&quot;;
        }

        sub stringify(UNIVERSAL $r) : multi {   # *any* type of object
                return $obj-&gt;stringify()
			if $obj-&gt;can('stringify');
                return &quot;???&quot;;
        }

        sub stringify($scalar) : multi {        # catch-all if ref() eq &quot;&quot;
                return qq{'$scalar'};
        }


        # and later...

        print stringify([1,2,3]);
        print stringify({a=&gt;1,b=&gt;[1,2,3],c=&gt;MyClass-&gt;new(),d=&gt;qr/#.*/});
        print stringify(42);</pre>
<p>Notes:</p>
<ul>
<li><a name='In the above example, stringify is used recursively in processing the contents of arrays and hashes. This ensures that nested components (as in the second of the &quot;and later...&quot; examples) are correctly stringified. This indicates some of the polymorphic power of multimethods, in that the single map-ped call to stringify suffices to correctly stringify every array element and hash entry, no matter what type that nested element or entry is.'></a>In the above example,
<code>stringify</code> is used recursively in processing the contents of
arrays and hashes. This ensures that nested components (as in the
second of the &quot;and later...&quot; examples) are correctly stringified.
This indicates some of the polymorphic power of multimethods, in that the
single <code>map</code>-ped call to <code>stringify</code> suffices to correctly stringify
every array element and hash entry, no matter what type that nested
element or entry is.</li>
<li><a name='The parameter type UNIVERSAL provides a means of writing a single variant that captures references to any blessed object, since every blessed object automatically inherits from UNIVERSAL.'></a>The parameter type <code>UNIVERSAL</code> provides a means of writing a single
variant that captures references to <i>any</i> blessed object, since every
blessed object automatically inherits from <code>UNIVERSAL</code>.</li>
<li><a name='A variant whose argument is untyped (i.e. the last variant in the above example) represents a &quot;catch-all&quot; case, which in this particular case would receive all calls to stringify which had non-reference scalar arguments. If the stringify(UNIVERSAL) variant did not exist, the untyped variant would also receive all calls with blessed objects as arguments.'></a>A variant whose argument is untyped (i.e. the last variant in the above
example) represents a &quot;catch-all&quot; case, which in this particular
case would receive all calls to <code>stringify</code> which had non-reference
scalar arguments. If the <code>stringify(UNIVERSAL)</code> variant did not exist,
the untyped variant would also receive all calls with blessed objects
as arguments.</li>
</ul>
<a name='Handling dispatch failure'></a><h2>Handling dispatch failure</h2>
<p>It's relatively easy to set up a multimethod such that particular
combinations of argument types cannot be correctly dispatched. For
example, consider the following variants of a multimethod called
<code>put_peg</code>:</p>
<pre>        package RoundPeg;     use base 'Peg';
        package SquareHole;   use base 'Hole';

        sub put_peg(RoundPeg,Hole) : multi {
                print &quot;round peg in generic hole\n&quot;
        }

        sub put_peg(Peg,SquareHole) : multi {
                print &quot;generic peg in square hole\n&quot;
        }

        sub put_peg(Peg,Hole) : multi {
                print &quot;generic peg in generic hole\n&quot;
        }</pre>
<p>If <code>put_peg</code> is called like this:</p>
<pre>        my $peg  = RoundPeg-&gt;new();
        my $hole = SquareHole-&gt;new();

        put_peg($peg, $hole);</pre>
<p>then the call can't be dispatched, because there's no way to
decide between the variants <code>(RoundPeg,Hole)</code> and <code>(Peg,SquareHole)</code>,
each of which is the same inheritance distance (i.e. 1 derivation) from
the actual arguments.</p>
<p>The response to this situation (proposed above) is to throw an exception
like this:</p>
<pre>        Cannot resolve call to multimethod put_peg(RoundPeg,SquareHole).
        The multimethods:
                put_peg(RoundPeg,Hole)
                put_peg(Peg,SquareHole)
        are equally viable</pre>
<p>This is the obvious behaviour, since the case truly <i>is</i> ambiguous.</p>
<p>Some languages (e.g. CLOS) take a different approach -- breaking the
tie by a recount on the inheritance distance of each argument
starting from the left. In this example, that would mean that
the call would be dispatched to <code>put_peg(RoundPeg,Hole)</code>, since
the left-most parameter of that variant is a &quot;closer&quot; match than the
left-most parameter of the <code>put_peg(Peg,SquareHole)</code> variant.</p>
<p>In the author's opinion, this approach is appalling, since it favours
one parameter above all others for no better reason than it comes first
in the argument list. But there is no reason why pegs should be more
significant than holes. Moreover, arbitrarily resolving the dispatch in
this way will often mask a fundamental design flaw in the multimethod.</p>
<p>However, experience indicates that sometimes the more specialized
variants of a multimethod are only provided as optimizations, and a more
general variant (in this case, the <code>(Peg,Hole)</code> variant) would suffice
as a default where such an ambiguity exists. It is proposed that an
additional parameterized attribute -- <code>:default(ambiguous)</code> -- be
provided so that one particular multimethod can be nominated as the
dispatch recipient in cases of ambiguity:</p>
<pre>        sub put_peg(Peg,Hole) : multi default(ambiguous) {
                print &quot;some kinda peg in some kinda hole\n&quot;
        }</pre>
<p>Now, whenever a call to <code>put_peg</code> can't be dispatched because it's
ambiguous, this default variant will be called, rather than throwing an
exception.</p>
<p>Multiple dispatch can also fail if there are <i>no</i> suitable variants
available to handle a particular call. For example:</p>
<pre>        my $peg  = JPEG-&gt;new();
        my $hole = Loophole-&gt;new();

        put_peg($peg, $hole);</pre>
<p>which, it is proposed above, would normally produce the exception:</p>
<pre>        No viable candidate for call to multimethod put_peg(JPEG,Loophole)</pre>
<p>The classes JPEG and Loophole aren't in the Peg and Hole hierarchies, so
there's no inheritance path back to a more general <code>(Peg,Hole)</code> variant.</p>
<p>It is proposed that the <code>:default</code> attribute might also take an
parameter <code>failure</code>, which would indicate that the attributed variant
should be called when dispatch fails to find any suitable variant:</p>
<pre>        sub put_peg(@args) : multi default(failure) {
		print &quot;Unknown kinda peg in unknown kinda hole\n&quot;;
        }</pre>
<p>It is further proposed that a single variant could cover <i>both</i> types
of default behaviour, if it were specified with just the (unparameterized)
<code>default</code> attribute:</p>
<pre>        sub put_peg(@args) : multi default {
		print &quot;Any kinda peg in any kinda hole\n&quot;;
        }</pre>
<a name='Multimethod redispatch'></a><h2>Multimethod redispatch</h2>
<p>It is further proposed that the semantics of the proposed NEXT pseudoclass
(RFC 190) be extended to cover redispatch of multimethods.</p>
<p>Specifically, it is proposed that within a multimethod variant, any call
of the form <code>&amp;NEXT::foo;</code> to the same multimethod would cause the
dispatch mechanism to resume its dispatch process at the next most viable
candidate(s) and thus select the next closest variant.</p>
<p>For example, given the following multimethods:</p>
<pre>        package Object;
        package HardObject;     use base 'Object';
        package SoftObject;     use base 'Object';

	package Simulation;

        sub collide(Object $obj1, Object $obj2) {
                print STDLOG &quot;$obj1-&gt;{id} collided with $obj2-&gt;{id}&quot;;
        }

        sub collide(HardObject $obj1, HardObject $obj2) {
                print &quot;crunch!&quot;;
                &amp;NEXT::collide;         
        }

        sub collide(SoftObject $obj1, SoftObject $obj2) {
                print &quot;gloop!&quot;;
                &amp;NEXT::collide;
        }</pre>
<p>In this case, if one of the two more specialized collision variants
is called, the more general variant that logs all collisions would
also be invoked (and passed the same arguments).</p>
<a name='MIGRATION ISSUES'></a><h1>MIGRATION ISSUES</h1>
<p>None.</p>
<a name='IMPLEMENTATION'></a><h1>IMPLEMENTATION</h1>
<p>See the Class::Multimethods module.</p>
<a name='REFERENCES'></a><h1>REFERENCES</h1>
<p>&quot;Object Oriented Perl&quot;, Chapter 13.</p>
<p>RFC 128: Subroutines: Extend subroutine contexts to include name parameters and lazy arguments</p>
<p>RFC 190 : NEXT pseudoclass for method redispatch</p>
</div>
